<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 时间复杂度O(nlogn)
        // 空间复杂度O(n)


        // 归并排序，非递归写法，是先分成长度是1的子序列，然后在两两进行归并，再四个四个进行归并，
        function sortArray(nums) {
            if (nums.length <= 1) {
                return nums;
            }

            let len = nums.length;
            for (let size = 1; size < len; size *= 2) {
                for (let leftStart = 0; leftStart < len; leftStart += size * 2) {
                    let mid = Math.min(leftStart + size, len)
                    let rightEnd = Math.min(leftStart + size * 2, len)

                    let leftArr = nums.slice(leftStart, mid)
                    let rightArr = nums.slice(mid, rightEnd)
                    let tempArr = merge(leftArr, rightArr)

                    for (let i = 0; i < tempArr.length; i++) {
                        nums[i + leftStart] = tempArr[i]
                    }
                }
            }



            // 初始子数组长度为1
            return nums;
        }

        // 定义一个辅助函数用于合并两个有序数组
        function merge(leftArr, rightArr) {
            // 对left和right数组进行归并操作
            let i = 0, j = 0;
            let result = [];
            while(i < leftArr.length && j < rightArr.length) {
                if (leftArr[i] < rightArr[j]) {
                    result.push(leftArr[i])
                    i++
                } else {
                    result.push(rightArr[j])
                    j++ 
                }
            }

            // 剩余没有处理完的数组
            while (i < leftArr.length) {
                result.push(leftArr[i])
                i++
            }

            while (j < rightArr.length) {
                result.push(rightArr[j])
                j++
            }

            return result;
        }
        let initArr = [3, 1, 6, 5, 7, 2, 9, 8]
        console.log(sortArray(initArr));
    </script>
</body>

</html>